The deflate compression (RFC1951) is a compression algorithm on which ZLIB (RFC1950) and GZIP (RFC1952) widely used in computers are based. The deflate compression is a combination of two kinds of compression algorithms, and LZ77 encoding is used in the first half of the deflate compression. The LZ77 encoding is to compress data by searching for an iterative character sequence part of the data and replacing the iterative character sequence part with the position and length of the iterative character sequence part. For example, in LZ77 encoding of a character sequence “IBM is IBM”, the “IBM” that occurs the second time is an iterative character sequence part and therefore is compressed. More specifically, the iterative character sequence part is replaced with a code, such as “7, 3” indicating that a character sequence having a length of three characters starting with the seventh character prior to the leading character of the iterative character sequence part, and thus is compressed. In this case, the greater the length of the iterative part, the higher the compression ratio is.
According to the specifications of the deflate compression, up to 32 kilobytes of preceding data is searched for an iterative character sequence part, and the search for an iterative character sequence part uses a large amount of character sequence comparison processing.
If the processing is performed by software, the processing can take a long time. Typically, software uses the hash method to reduce the search time. However, if there are many character sequences having the same hash value, the hash method may discard some of the character sequences. Thus, it is difficult to completely search the whole of a character.